﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.DataStructures.MergeFindSets;
using Algoritmia.Problems.Sorting;
using Algoritmia.Utils;

namespace Algoritmia.Problems.SpanningTrees.Kruskal
{
    public class KruskalMinimumSpanningForestFinder<T> : IMinimumSpanningForestFinder<T,double>
    {
        private readonly Func<IEnumerable<T>, IMergeFindSet<T>> _createMFSet;
        private readonly IInPlaceSorter<Tuple<T, T>> _sorter;
        private readonly EqualityComparison<T> _equalityComparison;

        public KruskalMinimumSpanningForestFinder(Func<IEnumerable<T>,IMergeFindSet<T>> createMFSet = null,
                                                  Func<IInPlaceSorter<Tuple<T, T>>> createSorter = null,
                                                  EqualityComparison<T> equalityComparison = null)
        {
            _createMFSet = createMFSet ?? (it => new MergeFindSet<T>(from e in it
                                                                     select new[] {e}));
            createSorter = createSorter ?? (() => new SemiIterativeInPlaceQuickSorter<Tuple<T,T>>());
            _sorter = createSorter();
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
        }

        #region Implementation of IMinimumSpanningForestFinder<T,double>

        public IEnumerable<Tuple<T, T>> MinimumSpanningForest(IDigraph<T> g, WeightingFunction<T, double> w)
        {
            var forest = _createMFSet(g.V);
            int yielded = 0;
            var sortedEdges = g.E.ToAlgoritmiaList();
            _sorter.Sort(sortedEdges,(e1,e2) => w(e1.Item1,e1.Item2).CompareTo(w(e2.Item1,e2.Item2)));
            foreach(var edge in sortedEdges)
            {
                var u = edge.Item1;
                var v = edge.Item2;
                if (  !_equalityComparison(forest.Find(u),forest.Find(v)) )
                {
                    yield return new Tuple<T,T>(u,v);
                    yielded++;
                    forest.Merge(u,v);
                    if ( yielded == g.V.Count-1)
                    {
                        break;
                    }
                }
            }

        }

        #endregion
    }
}
